package fun.codedesign.jdk.math.algorithm.sort;

/**
 * 堆排序 <br>
 * <pre>
 *     将数组转换为一个二叉树进行排序，二叉树数组公式：父节点索引i, leftChild = 2i+1, rightChild = leftChild+1
 *     所以最后一个节点的父节点为， ((arr.length-1)-1)/2 = arr.length/2-1   arr.length-1当作左节点
 *     <a href = "https://www.cnblogs.com/chengxiao/p/6129630.html"></a>
 * </pre>
 *
 * @author zengjian
 * @create 2018-06-26 11:33
 * @since 1.0.0
 */
public class HeapSorter implements Sorter {
    @Override
    public void sort(int[] arr) {
        // 构建大顶堆
        for (int endRoot = arr.length / 2 - 1; endRoot >= 0; endRoot--) {
            // 从最后一个根节点开始调整其位置
            adjustHeap(arr, endRoot, arr.length);
        }

        // 交换顶堆及最后值
        for (int i = arr.length - 1; i >= 0; i--) {
            swap(0, i, arr);
            // 已经排好序，所以只需要从第一个节点开始调整即可
            adjustHeap(arr, 0, i);
        }
    }

    private void swap(int start, int last, int[] arr) {
        int temp = arr[start];
        arr[start] = arr[last];
        arr[last] = temp;
    }

    /**
     * i是最后一个根节点
     *
     * @param arr
     * @param i
     * @param length
     */
    private void adjustHeap(int[] arr, int root, int length) {
        int temp = arr[root];
        // 循环调整更大的子节点往堆顶走
        for (int leftChild = 2 * root + 1; leftChild < length; leftChild = 2 * leftChild + 1) {
            // 如果左节点更小，取右节点进行比较
            if (leftChild + 1 < length && arr[leftChild] < arr[leftChild + 1]) {
                leftChild++;
            }
            // 取两节点中更大的节点与父节点比较，如果比父节点大，那父节点给更大的位置
            if (arr[leftChild] > temp) {
                // 原来的节点位置给孩子节点
                arr[root] = arr[leftChild];
                // 孩子节点给父节点
                root = leftChild;
            } else {
                break;
            }
        }
        // 循环交换至最后
        // 孩子节点赋原来root值
        arr[root] = temp;
    }

}
